U.S. patent application Ser. No. 09/364157, which is assigned to the assignee of the present application, discloses a real time aircraft optimization engine that uses Unary, Binary, and Three-Way Operations for repairing a Grounded Aircraft Route, a route of an aircraft which has been grounded for a specific period of time. The Unary Operations cancel and uncancel or do nothing to the Grounded Aircraft Routes. The Binary Operations repair a Grounded Aircraft Route through actions performed with one Available Aircraft Route, a route of an aircraft which is available for use in a solution of a flight schedule irregularity. Tertiary Operations are used to repair a Grounded Aircraft Route through actions with two Available Aircraft Routes. The system in which the aircraft optimization engine of the above patent application operates is illustrated in FIG. 1.
Referring to FIG. 1, a functional block diagram of the environment in which the invention operates is shown, where a user interface referred to as an Optimization Server 1 is in electrical communication with a user by way of a bi-directional communication path 2, and receives a request for optimal solutions to a specific flight schedule disruption. In response to the request, the Optimization Server 1 initializes an Aircraft Optimization Engine 3 by way of a bi-directional communication path 4, and provides the Aircraft Optimization Engine 3 an Aircraft Problem Specification. The Aircraft Optimization Engine 3 processes the Aircraft Problem Specification and generates a set of optimal solutions including aircraft reassignments and flight modifications to overcome the disruption. The solutions are transmitted over communication path 4, and through the Optimization Server 1 and bi-directional path 2 to the user.
The Aircraft Optimization Engine 3 further initializes a Crew Optimization Engine 5 by way of a bi-directional communication path 6 to determine whether the optimal flight solutions are efficiently supported by flight and service crews.
During operation, the Aircraft Optimization Engine 3 and the Crew Optimization Engine communicate by way of bi-directional communication paths 10 and 11, respectively, with a memory system such as a disk storage unit 9 having stored therein memory objects containing all of the data used by the engines to solve problems. For example, the memory objects include instances of Station, Market, Aircraft, Fleet, Subfleet, Maintenance, and Flight classes, and are created and updated by the Data Collection Unit 12 and the Data Update Unit 13, respectively.
The Data Collection Unit 12 receives complete information for stations, markets, aircraft, fleets, subfleets, maintenance, and flights from the user by way of bi-directional communication path 14. Thereafter, the Data Collection Unit 12 creates memory objects which are supplied by way of a bi-directional communication path 15 for storage in the disk storage unit 9, and at memory locations specified by a Memory Mapping Unit 16 along a bi-directional communication path 17. Further, the Data Update Unit 13 receives revisions to the memory objects from the user over a bi-directional communication path 18, and supplies corrections through a bi-directional communication path 19 to the objects identified by the Memory Mapping Unit 16.
The Memory Mapping Unit 16 receives control signals from the user over a bi-directional communication path 20, and in response thereto identifies the addresses of the memory objects in the disk storage unit 9 which are being operated upon. By means of the Memory Mapping Unit 16 and the Data Update Unit 13, the user is able to keep the data stored in the Disk Storage Unit 9 current with the data being supplied to the user by way of communication path 2.
At any given time, the memory objects of the Disk Storage Unit 9 reflect the existing flight environment, including identifications of protected flights which are not to be canceled or delayed; flight sequences or routes for each aircraft; the stations or airports to be used by the aircraft; the fleets and subfleets assigned to each station; station closure times; fleet arrival and departure curfews; inviolable and violable maintenance schedules; aircraft seat capacities; fleet operational ground times; operations costs; flight disruption costs; subfleet disruption costs; and revenue and passenger information for each scheduled flight.
The Aircraft Problem Specification received by the Aircraft Optimization Engine 3 upon being initialized by a request from the user, further includes the identification of grounded aircraft; the stations where aircraft groundings have occurred; the start and end times of each of such groundings; the identification of available aircraft; the identification of protected flights; recovery period start and end times; maximum allowable flight delays; and flight cancellation and ferry creation restraints.
Based upon the above information a solution comprised of flight delays and cancellations, Ferry Flight creations, as well as aircraft reassignments is produced
In the prior art invention disclosed in the above patent application, a solution is sought by first executing Unary Operations, then Binary Operations, and lastly Three-Way Operations until all Available Aircraft Routes have been processed to achieve solutions for all Grounded Aircraft Routes. See FIG. 3 of the above patent application. More particularly, Available Aircraft Routes are chosen two at a time, and a local neighborhood search is performed (i.e., the above set of operations are performed on the Grounded Aircraft Route to identify time and space feasible solutions), and thereafter two additional Available Aircraft Routes are chosen and the process repeated.
One Binary Operation that is disclosed is a Swap Operation in which flight sequences of one route are replaced with flight sequences of another route. A Three-Way Swap also is disclosed which is comprised of removing a first sequence of flights from a Grounded Aircraft Route, removing a second sequence of flights from a first Available Aircraft Route, removing a third sequence of flights from a second Available Aircraft Route, replacing the first sequence with the second sequence of flights, replacing the second sequence with the third sequence of flights, and replacing the third sequence with the first sequence of flights.
The above Three-Way Swap Operation requires three entities to be considered through a brute force method which is time consuming because three flights are considered at a same time, which is not tolerable in an environment demanding real time solutions such as occurs in aircraft flight schedules. In order to alleviate this problem, a solution is sought which would reduce problem complexity to a consideration of only two aircraft at a time by taking advantage of conditions found while performing Binary Operations that could be used in Tertiary Operations including Three-Way Swap Operations in accordance with the present invention. That is certain states found while performing Binary Operations are later used in Tertiary Operations in real time.